package demo1;
import java.util.*;

public class Sort {
    /*    private void mergeFunc(int[] array, int left, int right){
            //终止条件
            if(left == right){
                return;
            }
            int mid = (left + right) / 2;
            //分组递归，每组之间比较，调整组位置
            mergeFunc(array, left, mid);
            mergeFunc(array, mid + 1, right);
            //合并
            merge(array, left, right, mid);
        }
        private void merge(int[] array, int start, int end, int mid){
            int[] tmpArray = new int[end - start + 1];
            int s1 = start;
            int s2 = mid + 1;
            int index = 0;//临时数组的下标
            while(s1 <= mid && s2 <= end){
                //两组一对一对比较，一对中较小的元素放入数组
                if(array[s1] < array[s2]){
                    tmpArray[index++] = array[s1++];
                }else{
                    tmpArray[index++] = array[s2++];
                }
            }
            //两组比较完后，若还有未比较的元素，就直接加到临时数组后面
            while(s1 <= mid){
                tmpArray[index++] = array[s1++];
            }
            while(s2 <= end){
                tmpArray[index++] = array[s2++];
            }
            //最后覆盖数组原来的数据，将拍好序的元素直接放入
            for(int i = 0; i < index; i++){
                array[start + i] = tmpArray[i];
            }
        }
        public void mergeSort(int[] array){
            mergeFunc(array, 0, array.length - 1);
        }*/
    //归并排序2
/*    private void mergeFunc(int[] array, int left, int right) {
        if (left == right) {
            return;
        }
        //分组线
        int mid = (left + right) / 2;
        //递归分组
        mergeFunc(array, left, mid);
        mergeFunc(array, mid + 1, right);
        //合并
        merge(array, left, right, mid);
    }

    private void merge(int[] array, int start, int end, int mid) {
        int[] tmpArray = new int[end - start + 1];
        int s1 = start;
        int s2 = mid + 1;
        int k = 0;
        while (s1 <= mid && s2 <= end) {
            //每组中的每对进行比较，小的放入数组
            if (array[s1] < array[s2]) {
                tmpArray[k++] = array[s1++];
            } else {
                tmpArray[k++] = array[s2++];
            }
        }
        //剩下每比较的直接接在尾部
        while (s1 <= mid) {
            tmpArray[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmpArray[k++] = array[s2++];
        }
        //合并
        for (int i = 0; i < k; i++) {
            array[i + start] = tmpArray[i];
        }
    }
    public void insert(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    //JZ41 数据流中的中位数
    ArrayList<Integer> array = new ArrayList<Integer>();
    public void Insert(Integer num) {
        if(array.isEmpty()){
            array.add(num);
        }else{
            //每次对进来的数据进行插入排序,这样每个数字就是有序的
            int i = 0;
            for(; i < array.size(); i++){
                if(num <= array.get(i)){
                    break;
                }
            }
            array.add(i, num);
        }
    }

    public Double GetMedian() {
        int size = array.size();
        //判断是偶数还是奇数
        if(size % 2 == 0){
            //若是偶数，取出中间两个元素，即可得中位数
            int mid1 = size / 2;
            int mid2 = mid1 - 1;
            return (double)(array.get(mid1) + array.get(mid2)) / 2.0;
        }else{
            //若是偶数，直接返回中间下标的数即可
            int mid = size / 2;
            return (double)array.get(mid);
        }
    }*/
    //归并
    private void mergeFunc(int[] array, int left, int right){
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        mergeFunc(array, left, mid);
        mergeFunc(array, mid + 1, right);
        merge(array, left, right, mid);
    }
    private void merge(int[] array, int start, int end, int mid){
        int[] tmpArr = new int[end - start + 1];
        int s1 = start;
        int s2 = mid + 1;
        int k = 0;
        while(s1 <= mid && s2 <= end){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];
            }else{
                tmpArr[k++] = array[s2++];
            }
        }
        while(s1 <= mid){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= end){
            tmpArr[k++] = array[s2++];
        }
        for(int i = 0; i < tmpArr.length; i++){
            array[start + i] = tmpArr[i];
        }
    }

    public void mergeSort(int[] array){
        mergeFunc(array, 0, array.length - 1);
    }

    //插入排序
    public void insertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--) {
                if(array[j] >= key) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = key;
        }
    }



}











